package medium

/*
时间复杂度：O(N)
空间复杂度：O(N)

解：单调栈+循环数组，如果一个元素x的右边找不到最大元素，则通过循环数组，从索引0开始，在x左边找最大元素
例: 3 2 1  没有比3大的元素，右边第一个比2大的元素没有，所以要从数组开头找，即3，比1大的也是3
=》 -1 3 3
*/

func nextGreaterElements(nums []int) []int {
	n := len(nums)
	stack := make([]int, 0)
	ans := make([]int, n)
	for i := range ans {
		ans[i] = -1
	}
	for i := 0; i < 2*n-1; i++ {
		for len(stack) > 0 && nums[i%n] > nums[stack[len(stack)-1]] {
			ans[stack[len(stack)-1]] = nums[i%n]
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, i%n)
	}
	return ans
}
